In-memory key-value caches have become widely used to provide low-latency, high-throughput access to unstructured objects for the Internet-tier. For example, in many cases, a separate cache server (or set of such servers) that exists in front of the database tier may be used to cache database objects as they are read. This enables the cache server(s) to alleviate the load on the database tier. In order to provide low-latency operation, cached data may be maintained in a local volatile memory such as Dynamic Random Access Memory (DRAM), which provides for high-speed access to the cached data. However, the aggregate memory capacity of cache server(s) is often limited by various factors.